package Recursion;

public class MiGong {

  public static void main(String[] args) {
//    用一个二维数组模拟迷宫
    int[][]map = new int[8][7];
//    上下设置成墙，这里我们假设1为墙
    for (int i = 0; i < 7; i++) {
      map[0][i] = 1;
      map[7][i] = 1;
    }
//    左右设置为墙
    for (int i = 0; i < 8; i++) {
      map[i][0] = 1;
      map[i][6] = 1;
    }
//    设置挡板
    map[3][1] = 1;
    map[3][2] = 1;
//    map[2][2] = 1;
//    map[1][2] = 1;

//    打印地图
    System.out.println("地图的情况:");
    for (int[] row : map) {
      for (int col : row) {
        System.out.print(col + " ");
      }
      System.out.println();
    }

//    找路
//    setWay(map,1,1);
//    第二种策略找路
    setWay2(map,1,1);
//    打印出新地图
    System.out.println("新地图的情况:");
    for (int[] row : map) {
      for (int col : row) {
        System.out.print(col + " ");
      }
      System.out.println();
    }
  }




  /*
  1. map表示地图
  2.i,j表示从地图的哪个位置开始出发(1,1)
  3.如果小球能到map[6][5]位嚣,则说明通路找到。
  4.约定:当map[i][j]为0表示该点没有走过当为1表示墙 ﹔2表示通路可以走﹔3表示该点已经走过，但是走不通
  5.在走迷宫时，需要确定一个策略(方法)下->右->上->左，如果该点走不通，再回溯
   */
  public static boolean setWay(int[][] map,int i,int j){
    if (map[6][5] == 2){//道路已经找到
      return true;
    }
    if (map[i][j] == 0){//假定该点没有走过
//      按策略走：下->右->上->左
      map[i][j] = 2;//假定该点可以走
      if(setWay(map,i+1,j)){//向下
        return true;
      }else if(setWay(map,i,j+1)){//向右
        return true;
      }else if (setWay(map,i-1,j)){//向上
        return true;
      }else if (setWay(map,i,j-1)){//向左
        return true;
      }else {
        map[i][j] = 3;//该点走不通
        return false;
      }
    }else {
//      map[i][j] != 0 ,可能是1,2,3
      return false;
    }
  }

  /*
  修改走路策略，上->右->下->左
   */
  public static boolean setWay2(int[][] map,int i,int j){

    if (map[6][5] == 2){//道路已经找到
      return true;
    }
    if (map[i][j] == 0){//假定该点没有走过
//      按策略走：上->右->下->左
      map[i][j] = 2;//假定该点可以走
      if(setWay2(map,i-1,j)){//向上
        return true;
      }else if(setWay2(map,i,j+1)){//向右
        return true;
      }else if (setWay2(map,i+1,j)){//向下
        return true;
      }else if (setWay2(map,i,j-1)){//向左
        return true;
      }else {
        map[i][j] = 3;//该点走不通
        return false;
      }
    }else {
//      map[i][j] != 0 ,可能是1,2,3
      return false;
    }
  }
}
